package hot_100;

import java.util.Deque;
import java.util.LinkedList;

public class 接雨水 {
    public static void main(String[] args) {

    }

    public int trap(int[] height) {
        int length = height.length;
        Deque<Integer> deque = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < length; i++) {
            while (!deque.isEmpty() && height[deque.peekFirst()] <= height[i]) {
                Integer x = deque.pollFirst();
                if (deque.isEmpty()) {
                    break;
                }
                Integer j = deque.peekFirst();
                ans = (i - j - 1) * (Math.min(height[j], height[i]) - height[x]);
            }
            deque.addFirst(i);
        }
        return ans;
    }

//    public int trap(int[] height) {
//        int length = height.length;
//        Deque<Integer> deque = new LinkedList<>();
//        int ans = 0;
//        for (int i = 0; i < length; i++) {
//            while (!deque.isEmpty() && height[deque.peekFirst()] <= height[i]) {
//                Integer x = deque.pollFirst();
//                if (deque.isEmpty()) {
//                    break;
//                }
//                Integer j = deque.peekFirst();
//                ans = (i - j - 1) * (Math.min(height[j], height[i]) - height[x]);
//            }
//            deque.addFirst(i);
//        }
//        return ans;
//    }
}
